package com.leetcode.partition3;

import com.leetcode.common.TreeNode;

/**
 * @author `RKC`
 * @date 2021/8/17 10:24
 */
public class LC222完全二叉树的节点个数 {

    public int countNodes(TreeNode root) {
        return recursion(root);
    }

    private int recursion(TreeNode root) {
        if (root == null) return 0;
        int leftDepth = 0, rightDepth = 0;
        TreeNode left = root.left, right = root.right;
        while (left != null) {
            left = left.left;
            leftDepth++;
        }
        while (right != null) {
            right = right.right;
            rightDepth++;
        }
        if (leftDepth == rightDepth) {
            //树root是完全二叉树，完全二叉树的节点数=2^k - 1
            return (2 << leftDepth) - 1;
        }
        return recursion(root.left) + recursion(root.right) + 1;
    }
}
